Sample Method for Minimization of OBDDs
Identifieur interne : 002278 ( Main/Exploration ); précédent : 002277; suivant : 002279Sample Method for Minimization of OBDDs
Auteurs : Anna Slobodova [États-Unis, Slovaquie] ; Christoph Meinel [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1998.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Abstract: The exact minimization of the size of Ordered Binary Decision Diagrams (OBDD) is known to be an NP-complete problem. The available heuristical solutions of the problem still do not satisfy requirements of the practical applications. Development of the efficient algorithms that find acceptable variable orders within a short time and with a modest memory overhead is hence higly desired. In this paper we contribute to the solution of the minimization problem by a new variable reordering heuristic that is based on sampling. A small OBDD sample is chosen from the OBDDs that are considered for minimization. Solving the problem for this small sample, we obtain a variable order that is extrapolated and applied to the entire OBDDs. We present the first experimental results with the Sample Reordering targeted at combinatorial verification. The suggested heuristic is substantially faster than Sifting.
Url:
DOI: 10.1007/3-540-49477-4_34
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000F95
- to stream Istex, to step Curation: 000E85
- to stream Istex, to step Checkpoint: 000E49
- to stream Main, to step Merge: 002667
- to stream PascalFrancis, to step Corpus: 001063
- to stream PascalFrancis, to step Curation: 001731
- to stream PascalFrancis, to step Checkpoint: 000E60
- to stream Main, to step Merge: 002731
- to stream Main, to step Curation: 002278
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Sample Method for Minimization of OBDDs</title><author><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodova">Anna Slobodova</name></author><author><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1007/3-540-49477-4_34</idno><idno type="url">https://api.istex.fr/document/44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000F95</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000F95</idno><idno type="wicri:Area/Istex/Curation">000E85</idno><idno type="wicri:Area/Istex/Checkpoint">000E49</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000E49</idno><idno type="wicri:doubleKey">0302-9743:1998:Slobodova A:sample:method:for</idno><idno type="wicri:Area/Main/Merge">002667</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:99-0022994</idno><idno type="wicri:Area/PascalFrancis/Corpus">001063</idno><idno type="wicri:Area/PascalFrancis/Curation">001731</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000E60</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000E60</idno><idno type="wicri:doubleKey">0302-9743:1998:Slobodova A:sample:method:for</idno><idno type="wicri:Area/Main/Merge">002731</idno><idno type="wicri:Area/Main/Curation">002278</idno><idno type="wicri:Area/Main/Exploration">002278</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Sample Method for Minimization of OBDDs</title><author><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodova">Anna Slobodova</name><affiliation wicri:level="1"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Compaq, Shrewsbury, Massachusets</wicri:regionArea><wicri:noRegion>Massachusets</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Slovaquie</country><wicri:regionArea>Comenius University, Bratislava</wicri:regionArea><wicri:noRegion>Bratislava</wicri:noRegion></affiliation><affiliation></affiliation></author><author><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Institute of Telematics, Bahnhofstr 30-32, 54292, Trier</wicri:regionArea><wicri:noRegion>54292, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV - Informatik, University of Trier, 54286, Trier</wicri:regionArea><orgName type="university">Université de Trèves</orgName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1998</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8</idno><idno type="DOI">10.1007/3-540-49477-4_34</idno><idno type="ChapterID">34</idno><idno type="ChapterID">Chap34</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Algorithm performance</term><term>Binary decision diagram</term><term>Data structure</term><term>Domain decomposition</term><term>Heuristic method</term><term>Minimization</term><term>NP complete problem</term><term>Optimization</term><term>Sampling</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Algorithme</term><term>Diagramme binaire décision</term><term>Décomposition domaine</term><term>Echantillonnage</term><term>Minimisation</term><term>Méthode heuristique</term><term>Optimisation</term><term>Performance algorithme</term><term>Problème NP complet</term><term>Structure donnée</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The exact minimization of the size of Ordered Binary Decision Diagrams (OBDD) is known to be an NP-complete problem. The available heuristical solutions of the problem still do not satisfy requirements of the practical applications. Development of the efficient algorithms that find acceptable variable orders within a short time and with a modest memory overhead is hence higly desired. In this paper we contribute to the solution of the minimization problem by a new variable reordering heuristic that is based on sampling. A small OBDD sample is chosen from the OBDDs that are considered for minimization. Solving the problem for this small sample, we obtain a variable order that is extrapolated and applied to the entire OBDDs. We present the first experimental results with the Sample Reordering targeted at combinatorial verification. The suggested heuristic is substantially faster than Sifting.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>Slovaquie</li><li>États-Unis</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="États-Unis"><noRegion><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodova">Anna Slobodova</name></noRegion></country><country name="Slovaquie"><noRegion><name sortKey="Slobodova, Anna" sort="Slobodova, Anna" uniqKey="Slobodova A" first="Anna" last="Slobodova">Anna Slobodova</name></noRegion></country><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name></region><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name><name sortKey="Meinel, Christoph" sort="Meinel, Christoph" uniqKey="Meinel C" first="Christoph" last="Meinel">Christoph Meinel</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002278 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002278 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:44B0942DEB039718FDCA9D4A16B46A1CA0BB36F8
|texte= Sample Method for Minimization of OBDDs
}}
| This area was generated with Dilib version V0.6.31. |  |